1. Field of the Invention
The present invention relates to computer networks, and more particularly to dynamically assigning priority of load balancing Traffic Engineering (TE) label switched paths (LSPs) of a computer network.
2. Background Information
A computer network is a geographically distributed collection of nodes interconnected by communication links and segments for transporting data between end nodes, such as personal computers and workstations. Many types of networks are available, with the types ranging from local area networks (LANs) to wide area networks (WANs). LANs typically connect the nodes over dedicated private communications links located in the same general physical location, such as a building or campus. WANs, on the other hand, typically connect geographically dispersed nodes over long-distance communications links, such as common carrier telephone lines, optical lightpaths, synchronous optical networks (SONET), or synchronous digital hierarchy (SDH) links. The Internet is an example of a WAN that connects disparate networks throughout the world, providing global communication between nodes on various networks. The nodes typically communicate over the network by exchanging discrete frames or packets of data according to predefined protocols, such as the Transmission Control Protocol/Internet Protocol (TCP/IP). In this context, a protocol consists of a set of rules defining how the nodes interact with each other. Computer networks may be further interconnected by an intermediate network node, such as a router, to extend the effective “size” of each network.
Since management of interconnected computer networks can prove burdensome, smaller groups of computer networks may be maintained as routing domains or autonomous systems. The networks within an autonomous system (AS) are typically coupled together by conventional “intradomain” routers configured to execute intradomain routing protocols, and are generally subject to a common authority. To improve routing scalability, a service provider (e.g., an ISP) may divide an AS into multiple “areas.” It may be desirable, however, to increase the number of nodes capable of exchanging data; in this case, interdomain routers executing interdomain routing protocols are used to interconnect nodes of the various ASes. Moreover, it may be desirable to interconnect various ASes that operate under different administrative domains. As used herein, an AS or an area is generally referred to as a “domain,” and a router that interconnects different domains together is generally referred to as a “border router.”
An example of an interdomain routing protocol is the Border Gateway Protocol version 4 (BGP), which performs routing between domains (ASes) by exchanging routing and reachability information among neighboring interdomain routers of the systems. An adjacency is a relationship formed between selected neighboring (peer) routers for the purpose of exchanging routing information messages and abstracting the network topology. The routing information exchanged by BGP peer routers typically includes destination address prefixes, i.e., the portions of destination addresses used by the routing protocol to render routing (“next hop”) decisions. Examples of such destination addresses include IP version 4 (IPv4) and version 6 (IPv6) addresses. BGP generally operates over a reliable transport protocol, such as TCP, to establish a TCP connection/session. The BGP protocol is well known and generally described in Request for Comments (RFC) 1771, entitled A Border Gateway Protocol 4 (BGP-4), published March 1995.
Examples of an intradomain routing protocol, or an interior gateway protocol (IGP), are the Open Shortest Path First (OSPF) routing protocol and the Intermediate-System-to-Intermediate-System (IS-IS) routing protocol. The OSPF and IS-IS protocols are based on link-state technology and, therefore, are commonly referred to as link-state routing protocols. Link-state protocols define the manner with which routing information and network-topology information are exchanged and processed in a domain. This information is generally directed to an intradomain router's local state (e.g., the router's usable interfaces and reachable neighbors or adjacencies). The OSPF protocol is described in RFC 2328, entitled OSPF Version 2, dated April 1998 and the IS-IS protocol used in the context of IP is described in RFC 1195, entitled Use of OSI IS-IS for routing in TCP/IP and Dual Environments, dated December 1990, both of which are hereby incorporated by reference.
An intermediate network node often stores its routing information in a routing table maintained and managed by a routing information base (RIB). The routing table is a searchable data structure in which network addresses are mapped to their associated routing information. However, those skilled in the art will understand that the routing table need not be organized as a table, and alternatively may be another type of searchable data structure. Although the intermediate network node's routing table may be configured with a predetermined set of routing information, the node also may dynamically acquire (“learn”) network routing information as it sends and receives data packets. When a packet is received at the intermediate network node, the packet's destination address may be used to identify a routing table entry containing routing information associated with the received packet. Among other things, the packet's routing information indicates the packet's next-hop address.
To ensure that its routing table contains up-to-date routing information, the intermediate network node may cooperate with other intermediate nodes to disseminate routing information representative of the current network topology. For example, suppose the intermediate network node detects that one of its neighboring nodes (i.e., adjacent network nodes) becomes unavailable, e.g., due to a link failure or the neighboring node going “off-line,” etc. In this situation, the intermediate network node can update the routing information stored in its routing table to ensure that data packets are not routed to the unavailable network node. Furthermore, the intermediate node also may communicate this change in network topology to the other intermediate network nodes so they, too, can update their local routing tables and bypass the unavailable node. In this manner, each of the intermediate network nodes becomes “aware” of the change in topology.
Typically, routing information is disseminated among the intermediate network nodes in accordance with a predetermined network communication protocol, such as a link-state protocol (e.g., IS-IS, or OSPF). Conventional link-state protocols use link-state advertisements or link-state packets (or “IGP Advertisements”) for exchanging routing information between interconnected intermediate network nodes (IGP nodes). As used herein, an IGP Advertisement generally describes any message used by an IGP routing protocol for communicating routing information among interconnected IGP nodes, i.e., routers and switches. Operationally, a first IGP node may generate an IGP Advertisement and “flood” (i.e., transmit) the packet over each of its network interfaces coupled to other IGP nodes. Thereafter, a second IGP node may receive the flooded IGP Advertisement and update its routing table based on routing information contained in the received IGP Advertisement. Next, the second IGP node may flood the received IGP Advertisement over each of its network interfaces, except for the interface at which the IGP Advertisement was received. This flooding process may be repeated until each interconnected IGP node has received the IGP Advertisement and updated its local routing table.
In practice, each IGP node typically generates and disseminates an IGP Advertisement whose routing information includes a list of the intermediate node's neighboring network nodes and one or more “cost” values associated with each neighbor. As used herein, a cost value associated with a neighboring node is an arbitrary metric used to determine the relative ease/burden of communicating with that node. For instance, the cost value may be measured in terms of the number of hops required to reach the neighboring node, the average time for a packet to reach the neighboring node, the amount of network traffic or available bandwidth over a communication link coupled to the neighboring node, etc.
As noted, IGP Advertisements are usually flooded until each intermediate network IGP node has received an IGP Advertisement from each of the other interconnected intermediate nodes. Then, each of the IGP nodes (e.g., in a link-state protocol) can construct the same “view” of the network topology by aggregating the received lists of neighboring nodes and cost values. To that end, each IGP node may input this received routing information to a “shortest path first” (SPF) calculation that determines the lowest-cost network paths that couple the intermediate node with each of the other network nodes. For example, the Dijkstra algorithm is a conventional technique for performing such an SPF calculation, as described in more detail in Section 12.2.4 of the text book Interconnections Second Edition, by Radia Perlman, published September 1999, which is hereby incorporated by reference as though fully set forth herein. Each IGP node updates the routing information stored in its local routing table based on the results of its SPF calculation. More specifically, the RIB updates the routing table to correlate destination nodes with next-hop interfaces associated with the lowest-cost paths to reach those nodes, as determined by the SPF calculation.
Multi-Protocol Label Switching (MPLS) Traffic Engineering has been developed to meet data networking requirements such as guaranteed available bandwidth or fast restoration. MPLS Traffic Engineering exploits modern label switching techniques to build guaranteed bandwidth end-to-end tunnels through an IP/MPLS network of label switched routers (LSRs). These tunnels are a type of label switched path (LSP) and thus are generally referred to as MPLS Traffic Engineering (TE) LSPs. Examples of MPLS TE can be found in RFC 3209, entitled RSVP-TE: Extensions to RSVP for LSP Tunnels dated December 2001, RFC 3784 entitled Intermediate-System-to-Intermediate-System (IS-IS) Extensions for Traffic Engineering (TE) dated June 2004, and RFC 3630, entitled Traffic Engineering (TE) Extensions to OSPF Version 2 dated September 2003, the contents of all of which are hereby incorporated by reference in their entirety.
Establishment of an MPLS TE-LSP from a head-end LSR to a tail-end LSR involves computation of a path through a network of LSRs. Optimally, the computed path is the “shortest” path, as measured in some metric, that satisfies all relevant LSP Traffic Engineering constraints such as e.g., required bandwidth, “affinities” (administrative constraints to avoid or include certain links), etc. Path computation can either be performed by the head-end LSR or by some other entity operating as a path computation element (PCE) not co-located on the head-end LSR. The head-end LSR (or a PCE) exploits its knowledge of network topology and resources available on each link to perform the path computation according to the LSP Traffic Engineering constraints. Various path computation methodologies are available including CSPF (constrained shortest path first). MPLS TE-LSPs can be configured within a single domain, e.g., area, level, or AS, or may also span multiple domains, e.g., areas, levels, or ASes.
The PCE is an entity having the capability to compute paths between any nodes of which the PCE is aware in an AS or area. PCEs are especially useful in that they are more cognizant of network traffic and path selection within their AS or area, and thus may be used for more optimal path computation. A head-end LSR may further operate as a path computation client (PCC) configured to send a path computation request to the PCE, and receive a response with the computed path, which potentially takes into consideration other path computation requests from other PCCs. It is important to note that when one PCE sends a request to another PCE, it acts as a PCC.
Some applications may incorporate unidirectional data flows configured to transfer time-sensitive traffic from a source (sender) in a computer network to a destination (receiver) in the network in accordance with a certain “quality of service” (QoS). Here, network resources may be reserved for the unidirectional flow to ensure that the QoS associated with the data flow is maintained. The Resource reSerVation Protocol (RSVP) is a network-control protocol that enables applications to reserve resources in order to obtain special QoS for their data flows. RSVP works in conjunction with routing protocols to, e.g., reserve resources for a data flow in a computer network in order to establish a level of QoS required by the data flow. RSVP is defined in R. Braden, et al., Resource ReSerVation Protocol (RSVP), RFC 2205, which is hereby incorporated by reference in its entirety. In the case of traffic engineering applications, RSVP signaling is used to establish a TE-LSP and to convey various TE-LSP attributes to routers, such as border routers, along the TE-LSP obeying the set of required constraints whose path may have been computed by various means.
As defined in RFC 2205, an RSVP data flow is “admitted” and resources allocated to the data flow using a capacity-based admission control technique. According to this technique, resources are allocated to data flows on a “first-come-first-admitted” basis until the capacity of the resources is exhausted. S. Herzog, RSVP Extensions for Policy Control, RFC 2750, which is hereby incorporated by reference in its entirety, defines an extension to RFC 2205 that incorporates policy-based admission control. Through this extension to RSVP, admission control involves reserving resources on a policy basis in addition to using capacity as a basis. A simple example of such is an authentication/authorization policy. If a requestor attempts to reserve bandwidth but is unknown to the administration or makes an unauthorized request, the request will be denied based on the authentication/authorization policy even though bandwidth is available. But among authorized requesters, bandwidth is granted on a first-come-first-admitted basis.
A policy often employed in conjunction with RFC 2750 is a preemption-priority-based policy described in S. Herzog, Signaled Preemption Priority Policy Element, RFC 3181, which is hereby incorporated by reference in its entirety. The preemption-priority-based policy incorporates a technique that allows a new reservation to preempt one or more existing lower priority reservations in order to acquire resources reserved for the lower priority reservations. According to the technique, a preemption-priority value is associated with a new reservation and defending-priority values are associated with respective existing reservations. The reservations' preemption and defending priority values may be assigned in various ways known in the art. The preemption-priority value for the new reservation is compared with the defending-priority values of existing reservations to determine if the new reservation “preempts” any existing lower priority reservations. If so, resources allocated to selected lower priority reservations are reallocated for the new reservation. Notably, techniques for preemptions applied to MPLS TE-LSPs are described in detail in above-incorporated RFC 3209.
In practice, for example in the case of MPLS TE-LSP, an RSVP signaling message (e.g., a Path message) contains a specified preemption-priority value associated with the new TE-LSP. A network node that receives the message may first determine if sufficient unallocated resources are immediately available to satisfy the resources requested in the message. If not, the node then may identify lower priority existing reservations (TE-LSPs) that may be preempted to meet the needs of the new reservation. This may be done by comparing the new TE-LSP preemption priority value with the defending priority value of existing TE-LSPs to determine if the new TE-LSP is higher in priority than the existing TE-LSP. If so, the network node may preempt the existing TE-LSP by “tearing it down” and reallocating the resources associated with the torn down TE-LSP(s) to the new TE-LSP. Thereafter, an error message (e.g., a Path Error message) is sent upstream along the data path to notify the upstream nodes, including the source node, of the preemption.
Notably, the above-described preemption technique may cause lower priority reservations to be preempted immediately (“hard” preemption), thus causing unnecessary disruption to data flows associated with these reservations. For example, to “reclaim” the resources lost due to preemption, the lower priority TE-LSPs would have to be reestablished, causing a possible interruption to the data flow. A method to alleviate this situation is described in Meyer, et al. MPLS Traffic Engineering Soft Preemption <draft-ietf-mpls-soft-preemption-04.txt>, Internet Draft, April 2005, which is hereby incorporated by reference in its entirety. Briefly, the method described therein introduces a “preemption pending” state to create a “soft” preemption, which helps to more gracefully mitigate the reroute process of the displaced data flows carried within the preempted TE-LSP(s). Particularly, for a specified period of time while soft preemption is activated, head-end LSRs of soft preempted data flows are notified of the preemption and given the opportunity to reroute the data flow before it is hard preempted. In essence, reservations along the higher priority data flow are overbooked until the lower priority data flow has been given a chance to be rerouted.
Often, computation of TE-LSPs (data flows) are non-synchronized, such that each TE-LSP path is calculated separately from one another, either by multiple head-end nodes, or by a single head-end node or PCE, but at different times. As a result of the non-synchronized computations, resources, e.g., bandwidth, may become fragmented, which may lead to a “blocking” state where some TE-LSPs may not be established (or resized). For example, assume that there are two links from one location to another, where each link has an available 10 Mega-bytes per second (MBps) of bandwidth. Further assume that a first TE-LSP is established over the first link reserving 3 MBps, and a second TE-LSP is established over the second link reserving another 3 MBps. Each link thus has 7 MBps of bandwidth available, and the total available bandwidth across both links is 14 MBps. Should a third TE-LSP attempt to be established reserving 8 MBps of bandwidth, however, neither the first or second links could support such a reservation, even though across both links there is a combined available bandwidth of 14 MBps. This is because the 14 MBps of available bandwidth has been fragmented across the two links (into two 7 MBps links), preventing the ability to find a satisfactory path (of 8 MBps).
It would be possible to satisfy the third TE-LSP of 8 MBps if the other TE-LSPs could be displaced and “re-packed” accordingly onto a single link. In this case, for instance, the first link would have 4 MBps of available bandwidth (10−3−3), and the second link would have 2 MBps (10−8). One way to achieve this situation involves allocating different priorities to the TE-LSPs based on their bandwidth sizes, so as to increase the possibility of being able to place larger TE-LSPs that could preempt lower priority (hence smaller) TE-LSPs. Once preempted, the smaller TE-LSPs would have a better chance of finding a satisfactory path and would thus be rerouted, thereby creating a form of re-packing. Currently, this approach is static and requires an arbitrary priority assignment by a system administrator with knowledge of the network. Moreover, such a static configuration may lead to situations where a large number of smaller TE-LSPs is preempted, which may not be re-routable in order to place the larger TE-LSP.